The A* algorithm is a heuristic search most often used for finding shortest-path routes. If the heuristic guarantees a lower bound on the costs of any node below, then this can be used to prune whole branches where the heurisic exceeds the current best solution. That is, it can be seen as heuristic version of branch and bound. Often the raw heauristic is about the path beyond the node, for example the crows-fly distance to the target location in geographic shortest path search, in which case the distance along the path to the node has to be added to the raw heuristic to create a total path lower bound. The heauristic can also be used to guide the next node to explore in a variant of hill climbing.
Defined on page 72
Used on page 72
Also known as a${}^\ast$ algorithm
Using the A* algorithm to fnd shortest distance between Applethwaite and Gilby The straight-line disance between Cardale to Gilby is 50 miles, so any routes found must be longer than this. Therefore the Applethwaite--Barton --Gilby route is shorter than any route via Cardale, hence Cardale can be pruned.